Search results for "Super-recursive algorithm"

showing 5 items of 5 documents

Space-Efficient 1.5-Way Quantum Turing Machine

2001

1.5QTM is a sort of QTM (Quantum Turing Machine) where the head cannot move left (it can stay where it is and move right). For computations is used other - work tape. In this paper will be studied possibilities to economize work tape space more than the same deterministic Turing Machine can do (for some of the languages). As an example language (0i1i|i ≥ 0) is chosen, and is proved that this language could be recognized by deterministic Turing machine using log(i) cells on work tape , and 1.5QTM can recognize it using constant cells quantity.

TheoryofComputation_COMPUTATIONBYABSTRACTDEVICESTheoretical computer scienceQuantum Turing machineSuper-recursive algorithmComputer scienceProbabilistic Turing machineComputationDescription numberMultitape Turing machineDSPACElaw.inventionTuring machinesymbols.namesakeNon-deterministic Turing machinelawAlgorithm characterizationsPSPACEWolfram's 2-state 3-symbol Turing machineTuring machine examplesNSPACETuring reductionsymbolsUniversal Turing machineTime hierarchy theoremAlternating Turing machineRegister machine
researchProduct

Quantum Real - Time Turing Machine

2001

The principles of quantum computation differ from the principles of classical computation very much. Quantum analogues to the basic constructions of the classical computation theory, such as Turing machine or finite 1-way and 2-ways automata, do not generalize deterministic ones. Their capabilities are incomparable. The aim of this paper is to introduce a quantum counterpart for real - time Turing machine. The recognition of a special kind of language, that can't be recognized by a deterministic real - time Turing machine, is shown.

TheoryofComputation_COMPUTATIONBYABSTRACTDEVICESTheoretical computer scienceQuantum Turing machineDTIMEComputer scienceProbabilistic Turing machine2-EXPTIMESuper-recursive algorithmComputationDescription numberDSPACElaw.inventionsymbols.namesakeTuring machineTuring completenessNon-deterministic Turing machinelawAlgorithm characterizationsQuantumPSPACEQuantum computerFinite-state machineTuring machine examplesNSPACETheoryofComputation_GENERALAutomatonTheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGESTuring reductionTheory of computationsymbolsUniversal Turing machineTime hierarchy theoremAlternating Turing machineComputer Science::Formal Languages and Automata TheoryRegister machine
researchProduct

Minimal nontrivial space complexity of probabilistic one- way turing machines

2005

Languages recognizable in o(log log n) space by probabilistic one — way Turing machines are proved to be regular. This solves an open problem in [4].

Discrete mathematicsTheoryofComputation_COMPUTATIONBYABSTRACTDEVICESSuper-recursive algorithmProbabilistic Turing machineLinear speedup theoremNSPACEDescription numberCombinatoricsTuring machinesymbols.namesakeTheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGESNon-deterministic Turing machinesymbolsTime hierarchy theoremComputer Science::Formal Languages and Automata TheoryMathematics
researchProduct

Theory of Computation, Fuzziness and a physics of the immaterial

2013

In this paper we advance three clear-cut proposals as a contribution to the discussion on the role of notions of Computation and Fuzziness as a bridge between Hard and Soft Sciences. We suggest that an important difference between the two great fami- lies of science lies in their subject or research having a grounding in nature or not, and that Theory of Computation is a glaring exception to this classifi- cation, being a textbook hard science but dealing with the immaterial. We further advance that such unicity is strongly connected with Church-Turing thesis, and discuss about the role of Computation and Fuzziness as pillars of immaterial sciences

PhysicsStrongly connected componentTheoretical computer scienceHard and soft scienceSettore INF/01 - InformaticaHyperarithmetical theorySuper-recursive algorithmComputationSubject (philosophy)Bridge (interpersonal)EpistemologyTheory of computationTheory of Computation Fuzziness Church-Turing thesisMathematics
researchProduct

Ultrametric Finite Automata and Turing Machines

2013

We introduce a notion of ultrametric automata and Turing machines using p-adic numbers to describe random branching of the process of computation. These automata have properties similar to the properties of probabilistic automata but complexity of probabilistic automata and complexity of ultrametric automata can differ very much.

TheoryofComputation_COMPUTATIONBYABSTRACTDEVICESTheoretical computer scienceComputer scienceSuper-recursive algorithmProbabilistic Turing machineDescription numberNonlinear Sciences::Cellular Automata and Lattice GasesTuring machinesymbols.namesakeTheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGESTuring completenesssymbolsQuantum finite automataAutomata theoryTwo-way deterministic finite automatonComputer Science::Formal Languages and Automata TheoryMathematicsofComputing_DISCRETEMATHEMATICS
researchProduct